/**
 * @description: arrToTree
 * @author: huen2015
 */

interface IArrayData {
	id: number
	name: string
	parentId: number
}

interface ITreeData extends IArrayData {
	children?: IArrayData[]
}

/**
 * @description: arrToTreeData 根据 parentId、id 升序排序
 * @param: arr: IArrayData[] => IArrayData[]
 * @author: huen2015
 */
function sortArr(arr: IArrayData[]): IArrayData[] {
	return arr.sort((a: IArrayData, b: IArrayData) => {
		if (a.parentId > b.parentId) {
			return 1
		} else if (a.parentId === b.parentId) {
			return a.id - b.id
		} else {
			return -1
		}
	})
}

/**
 * @description: arrToTree
 * @param: arr: IArrayData[] => ITreeData | null
 * @author: huen2015
 */

function arrToTree(arr: IArrayData[]): ITreeData | null {
	const arrMapTree: Map<number, ITreeData> = new Map()
	// arr 排序
	const tempArr = sortArr(arr)
	let root: ITreeData | null = null

	tempArr.forEach((item: IArrayData) => {
		const { id, parentId } = item
		// 设置 arr 和 tree 的映射
		arrMapTree.set(id, item)
		// 查找当前 item 的父节点，并给父节点设置 children
		const parentTree = arrMapTree.get(parentId)
		if (parentTree) {
			if (!parentTree.children) {
				parentTree.children = []
			}
			parentTree.children.push(item)
		}

		// 根节点赋值
		if (parentId === 0) root = item
	})

	return root
}

const arrToTreeData: IArrayData[] = [
	{ id: 4, name: '武昌区', parentId: 2 },
	{ id: 5, name: '江岸区', parentId: 2 },
	{ id: 1, name: '湖北省', parentId: 0 }, // 0 代表顶级节点，无父节点
	{ id: 2, name: '武汉市', parentId: 1 },
	{ id: 3, name: '黄冈市', parentId: 1 },
	{ id: 6, name: '黄州区', parentId: 3 },
]

const arrToTreeResult = arrToTree(arrToTreeData)
console.log('arrToTreeResult', arrToTreeResult)

export { arrToTree }
